The present invention relates to the scheduling of transmissions without collisions in ad hoc computer networks with radio links, in which routers can have both hosts and networks attached to them.
Ad-hoc networks (i.e., multi-hop packet radio networks) are an ideal technology to provide a seamless extension of the Internet to the wireless mobile environment. In ad-hoc networks, nodes (e.g., stations or packet radios) can be mobile and communicate with one another either directly or through intermediate nodes, without relying on any preexisting network infrastructure. The self-configuring, dynamic-connectivity, multihop-propagation and fully-distributed nature of ad-hoc networks makes them very attractive for many new applications but also introduces difficult problems at the link and network layer.
Many medium-access control (MAC) protocols have been developed for wireless networks. The carrier-sense multiple access (CSMA) protocol was the first to be used in multihop packet-radio networks. A limitation of CSMA in multihop networks is that sources hidden from one another cannot detect their respective transmissions, which degrades CSMA""s performance to that of the pure ALOHA protocol. F. A. Tobagi and L. Kleinrock, xe2x80x9cPacket switching in radio channels: Part IIxe2x80x94the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution,xe2x80x9d IEEE Trans. Commun., vol. COM-23, no. 12, pp. 417-33, 1975. Many MAC protocols have been proposed and implemented to solve the hidden-terminal problems of CSMA.
The hardware characteristics of packet-radios are such that a packet-radio cannot transmit and listen to the same channel simultaneously; therefore, collision detection (e.g., CSMA/CD as described in R. M. Metcalfe and D. R. Boggs, xe2x80x9cETHERNET: Distributed packet switching for local computer networks,xe2x80x9d Communications of the ACM, vol. 19, no. 7, pp. 395-403, 1976) cannot be used in a single-channel packet-radio network. The throughput of CSMA protocols is very good, as long as the multiple transmitters within range of the same receivers can sense one another""s transmissions. Unfortunately, xe2x80x9chidden terminalxe2x80x9d problems (see Tobagi et al., supra) degrade the performance of CSMA substantially, because carrier sensing cannot prevent collisions in that case.
The busy tone multiple access (BTMA) protocol, id., was the first proposal to combat the hidden-terminal problems of CSMA. BTMA is designed for station-based networks and divides the channel into a message channel and the busy-tone channel. The base station transmits a busy-tone signal on the busy-tone channel as long as it senses carrier on the data channel. Because the base station is within a line of sight to all terminals, each terminal can sense the busy-tone channel to determine the state of the data channel. The limitations of BTMA are the use of a separate channel to convey the state of the data channel, the need for the receiver to transmit the busy tone while detecting carrier in the data channel, and the difficulty of detecting the busy-tone signal in a narrow-band channel.
A receiver initiated busy-tone multiple access protocol for packet-radio networks has also been proposed. C. Wu and V. O. K. Li, xe2x80x9cReceiver-initiated busy-tone multiple access in packet radio networks,xe2x80x9d ACM SIGCOMM 87 Workshop: Frontiers in Computer Communications Technology, Stowe, Vt., USA, Aug. 11-13 1987. In this scheme, the sender transmits a request-to-send (RTS) to the receiver, before sending a data packet. When the receiver obtains a correct RTS, it transmits a busy tone in a separate channel to alert other sources nearby that they should back off (i.e., refrain from transmitting). The correct source is always notified that it can proceed with transmission of the data packet. One of the limitations of this scheme is that it still requires a separate busy-tone channel and full-duplex operation at the receiver.
Several protocols have been proposed based on three-, four- or even five-way xe2x80x9ccollision-avoidancexe2x80x9d handshakes done with small control packets and meant to avoid data collisions when sources of data packets cannot hear one another. The collision-avoidance approach in each of these schemes follows the basic philosophy first introduced by Tobagi and Kleinrock in SRMA (Split-Channel Reservation Multiple Access). F. A. Tobagi and L. Kleinrock, xe2x80x9cPacket switching in radio channels: Part IIIxe2x80x94polling and (dynamic) split-channel reservation multiple access,xe2x80x9d IEEE Trans. Commun., vol. COM-24, no. 8, pp. 832-845, 1976. In SRMA, and subsequent collision-avoidance protocols, a sender node sends a request-to-send (RTS) packet to the intended receiver, either sensing the channel before sending the RTS or not sensing the channel before the RTS transmission. A receiver that hears a clean RTS responds with a clear-to-send (CTS), and the sender can send a data packet after hearing a clean CTS. Surprisingly, Tobagi and Kleinrock""s work on SRMA is not referenced by most subsequent proposals based on collision avoidance.
Other collision-avoidance schemes that have been proposed include the following: U.S. Pat. No. 5,319,641 discloses a method to improve CSMA p-persistent protocols by introducing a random waiting time that stations must wait listening to the channel once they have packets to send. The method disclosed does not work in networks with hidden terminals. U.S. Pat. No. 4,661,902 discloses a method that amounts to an implementation of SRMA over a single channel in which stations use carrier sensing before sending RTSs. P. Karn, xe2x80x9cMACAxe2x80x94a new channel access method for packet radio,xe2x80x9d in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL, 1990 discloses a technique that amounts to SRMA running over a single channel in which a request-to-send (RTS) packet is sent without carrier sensing. Karn includes no description of how to support packet trains, however. U.S. Pat. No. 5,231,634 discloses a method that also applies SRMA""s basic approach over a single channel. The RTS specifies the length of the impending data packet.
U.S. Pat. No. 5,502,724 discloses a method that extends the collision avoidance handshake to allow for multiple data packets to flow among a pair of communicating stations. A station that intends to establish a connection with a second station senses the channel. If the channel is idle, it sends a connection request (CR) packet to the intended receiver station. The CR specifies the number of data packets that the connection includes. The intended receiver sends a connection confirm (CC) packet to the sending station; the CC also specifies the number of packet in the connection. After the exchange of correct CR and CC packets the sending station may send one or multiple data packets and the receiving station may send an acknowledgment packet specifying which data packets were received correctly. To end the connection, the sending station sends a disconnect request (DR) and the receiving station issues a disconnect confirm (DC). Stations that receive a CR packet back off for an amount of time that is long enough for the advertised number of data packets to be sent to the receiver. After receiving a CR or CC, a station can attempt to access the channel when a timer proportional to the number of packets to be sent in the connection expire, or when it receives a DR or DC packet.
Some limitations with the method disclosed in U.S. Pat. No. 5,502,724 are that the method cannot ensure collision-fee transmissions of data packets, even with the transmission of CC packets by the receiver. The need for feedback from the receiver to its neighbors on a packet by packet basis was demonstrated by C. L. Fullmer and J. J. Garcia-Luna-Aceves in xe2x80x9cSolutions to Hidden Terminal Problems in Wireless Networksxe2x80x9d, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997. Because the CC packet sent by the receiver may collide with another packet at a neighbor of a receiver, the CC packet does not provide sufficient feedback to hidden nodes; furthermore, the need for feedback packets to be longer than request packets was demonstrated by the same authors in xe2x80x9cFloor Acquisition Multiple Access (FAMA) for Packet-Radio Networks,xe2x80x9d Proc. ACM SIGCOMM 95, Cambridge, Mass., Aug. 28-Sep. 1, 1995. Lastly, even though the disclosed method makes reference to broadcast packets sent to all the neighbors of a station, it provides no provisions to ensure that broadcast or multicast packets are received without interference by all the neighbors of a sending station.
U.S. Pat. No. 5,721,725 discloses a method similar to SRMA, and describes it to be an improvement over MACA. The method disclosed extends MACA by specifying in the RTS packets the desired data rate for data packets and allowing sender and receiver to negotiate the transmission data rate. As it is the case with other collision avoidance protocols discussed above, the method fails to guarantee collision free transmissions in networks with hidden terminals because no provisions are made on the length of the CTS being longer than the length of any RTS to ensure that collisions of RTSs and CTSs are detected by hidden stations.
DFWMAC IEEE802.11 (as described in K. C. Chen, xe2x80x9cMedium Access Control of Wireless LANs for Mobile Computing,xe2x80x9d IEEE Network, vol. 8, no. 5, pp. 50-63, 1994 and P802.11xe2x80x94Unapproved Draft: Wireless LAN Medium Access Control (MAC) and Physical Specifications, IEEE, January 1996), FAMA-NCS (discussed in C. L. Fullmer and J. J. Garcia-Luna-Aceves, xe2x80x9cSolutions to Hidden Terminal Problems in Wireless Networksxe2x80x9d, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997), and RIMA (described by J. J. Garcia-Luna-Aceves, in xe2x80x9cReversing the Collision Avoidance Handshake in Wireless Networks,xe2x80x9d Proc. ACM/IEEE Mobicom 99, August 1999) are three recent additional examples of collision-avoidance protocols. The scheme proposed in the draft 802.11 specification being considered by the Institute for Electrical and Electronic Engineers (IEEE) is a method very similar to SRMA with carrier sensing for the transmission of RTSs. The objective of FAMA-NCS is for a station that has data to send to acquire control of the channel in the vicinity of the receiver (which we call xe2x80x9cthe floorxe2x80x9d) before sending any data packet, and to ensure that no data packet collides with any other packet at the receiver. FAMA-NCS makes the length of CTSs much longer than the length of RTSs in order to detect the collision of RTSs with CTSs, which cannot be enforced in prior collision-avoidance protocols. RIMA consists of a family of protocols that reverse the collision-avoidance handshake method first introduced in SRMA and makes the receiver poll the sender of data.
Several other medium access control (MAC) protocols have been proposed for either single-channel wireless networks or wireline local area networks that are based on similar RTS-CTS exchanges, or based on RTSs followed by pauses. See, e.g., V. Bharghavan, et al., xe2x80x9cMACAW: A Media Access Protocol for Wireless LANs,xe2x80x9d Proc. ACM SIGCOMM ""94, pp. 212-25, London, UK, Aug. 31-Sep. 2, 1994; B. Vaduvur, xe2x80x9cAccess, Addressing and Security in Wireless Packet Networks,xe2x80x9d PhD thesis, University of California, Berkeley, Computer Science Department, 1995; A. Colvin, xe2x80x9cCSMA with collision avoidance,xe2x80x9d Computer Commun., vol. 6, no. 5, pp. 227-35, 1983; W. F. Lo and H. T. Mouftah, xe2x80x9cCarrier Sense Multiple Access with Collision Detection for Radio Channels,xe2x80x9d IEEE 13th Int""l Commun. and Energy Conf.? pp. 244-47, IEEE, 1984; R. Rom, xe2x80x9cCollision Detection in Radio Channels,xe2x80x9d Local Area and Multiple Access Networks, pp. 235-49, Computer Science Press, 1986; and G. S. Sidhu, R. F. Andrews, and A. B. Oppenheimer, Inside Apple Talk, Second Edition. Addison-Wesley Publishing Company, Inc., 1990.
Despite the popularity gained by collision-avoidance protocols and systems based on such protocols over the past few years, two key performance limitations of all collision-avoidance MAC protocols are: (a) they cannot provide channel-access delay guarantees, which represents a significant problem for real-time applications; and (b) they lack explicit support of collision-free multicasting or broadcasting, which implies that either a node must transmit the same multicast packet multiple times, once to each multicast-group neighbor, or packets are sent with likelihood of reception as low as the ALOHA protocol. In addition, collision-avoidance protocols require carrier sensing, which is not technically or economically feasible to implement in direct sequence spread spectrum radios with very high chip rates.
To circumvent hidden-terminal interference problems, unique codes (spreading codes or frequency-hopping sequences) can be assigned to receivers or senders. An example of this approach is the Metricom network. However, receiver oriented code assignment (ROCA) and transmitter oriented code assignment (TOCA) require either preconfiguring radios with the node-to-code mappings, or finding the codes being used by neighboring transmitters or receivers. Furthermore, efficient broadcasting is not guaranteed simply by establishing a TOCA approach, because all the neighbors of a transmitter must agree to listen to the transmitter at the same time to minimize the number of transmissions.
Another approach to channel access used in multihop wireless networks consists of establishing transmission schedules, i.e., allocating stations to different times and data channels (e.g., frequencies, spreading codes, or their combination) in a way that no collisions occur. Transmission scheduling can be static or dynamic; MAC protocols based on dynamic transmission scheduling explore the spatial reuse of the radio channel and thus have much higher channel utilization than such fixed scheduling approaches as TDMA and FDMA.
In TDMA protocols, time is divided into frames consisting of time slots. Time slots are allocated to specific nodes or a centralized station is used to allocate the time slots. The limitations of TDMA stem from the fixed assignment of time slots to nodes, which is slow to adapt to network changes and makes inefficient use of the channel if nodes are bursty sources of traffic, and the use of centralized assignments. There are many existing approaches based on dynamic TDMA methods in which stations use ALOHA, slotted ALOHA or other contention protocols in an uplink to request time slots from a base station. An example of this approach is the system disclosed in U.S. Pat. 5,638,371.
A number of protocols have been proposed in the recent past to provide dynamic time-slot allocation without requiring central base stations. These protocols can be classified as topology-independent and topology-dependent time scheduling protocols. Shepard (see, e.g., T. Shepard, xe2x80x9cA Channel Access Scheme for Large Dense Packet Radio Networks,xe2x80x9d SIGCOMM ""96 Conference Proc., ACM 1996; and U.S. Pat. No. 5,682,382), Chlamtac et al., xe2x80x9cTime-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks,xe2x80x9d IEEE/ACM Transactions on Networking, Vol. 5, no. 6, December, 1997, and Ji-Her Ju and Victor O. K. Li, xe2x80x9cAn Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks,xe2x80x9d IEEE/ACM Transactions on Networking, Vol. 6, no. 3, June 1998, have proposed topology-independent time-scheduling protocols. In these protocols, nodes are pre-assigned (by means of their nodal IDs, for example) or adopt a transmission schedule that they publish, and such a schedule specifies the times when a node transmits and receives. The protocols guarantee or provide a high likelihood that at least one transmission time in a node""s schedule does not conflict with any node one or two hops away.
In the Chlamtac and Ju and Li approaches, nodes are unable to determine which transmissions will succeed, complicating the job of higher layer (e.g., link-layer) protocols. These approaches also require values for the total number of nodes in the network and maximum number of neighbors for each node, as input parameters to the algorithm, thus making them design for the worst case conditions (and thus, operate inefficiently if the network is not as dense as expected), or being sensitive to actual network conditions (if the network is larger or more dense than expected). Shepard""s approach avoids collisions by assuming nodes are synchronized with their neighbors, have knowledge of their neighbors"" schedules, and are able to receive from multiple transmitting neighbors simultaneously. This final assumption requires fairly sophisticated radio hardware.
Recently, C. Zhu and M. S. Corson, xe2x80x9cA Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks,xe2x80x9d Proc. IEEE INFOCOM ""98 and Tang and Garcia-Luna-Aceves (see, e.g., Z. Tang and J. J. Garcia-Luna-Aceves, xe2x80x9cHop-Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networksxe2x80x9d, Proc. IEEE IC3N ""98: Seventh International Conference on Computer Communications and Networks, Lafayette, Louisiana, Oct. 12-15, 1998) have developed topology-dependent scheduling protocols, such that a node acquires a transmission schedule that allows the node to transmit without interferring with nodes one and two hops away from itself, and such that channel reuse is increased as the number of neighbors per node decreases. These protocols require nodes to contend in order to reserve collision-free time slots, and the contention is done on each mini-slot. Furthermore, they rely on dividing each slot into several mini-slots. All this limits the minimum duration that slots may have.
Several other TDMA approaches that require an initial, topology-independent schedule, followed by communication among the network nodes to negotiate a final schedule. For example, I. Chlamtac, xe2x80x9cFair Algorithms for Maximal Link Activation in Multihop Radio Networks,xe2x80x9d IEEE Transactions on Communications, Vol. COM-35, no. 7, July, 1987 proposed an algorithm based on a repeating link schedule that can adapt to traffic demands after some number of iterations of the algorithm. The algorithm starts with a xe2x80x9csingle-slot-perlinkxe2x80x9d schedule, such as provided by assigning each node a transmission slot according to its node ID. At each iteration, schedule information and a scheduling xe2x80x9ctokenxe2x80x9d are routed up and down a routing tree (established by means of pre-existing algorithms), to assign additional slots to nodes or links according to their degree of unmet traffic demands.
A. Ephremides and T. Truong, xe2x80x9cScheduling Broadcasts in Multihop Radio Networks,xe2x80x9d IEEE Transactions on Communications, Vol. COM-38, No. 4, April, 1990 proposed a similar algorithm in which each node is initially assigned a slot corresponding to its node ID, and then each node uses its assignment to pass xe2x80x9cskeletonxe2x80x9d schedules to its neighbors. During the next two frames (two iterations of communicating schedules), and in accordance with fixed node priorities, nodes are able to reserve available slots until all available slots are taken (i.e., no more slots can be assigned without causing collisions). Because of the need for schedules that are relatively fixed, requiring a few iterations to converge, and of scheduling-frame size equal to the maximum size of the network, these approaches have limited scalability and robustness to mobility or other dynamics.
The approach proposed by Young (see C. David Young, xe2x80x9cUSAP: a unifying dynamic distributed multichannel TDMA slot assignment protocolxe2x80x9d, MILCOM ""96 Conf. Proc., vol. 1, pp. 235-39, October 1996) also requires initial assignment of one slot per node, and then negotiation of scheduling packets for assignment of the other slots. However, the initially assigned slot is limited to the first slot in each xe2x80x9cframe.xe2x80x9d Thus, each node""s assigned slot occurs every N frames, where N is the maximum network size. Because of this, the approach is not scalable. Also, because a node needs to wait up to N frames before a proposed schedule addition is confirmed by a neighbor, the approach is relatively slow-adapting to dynamic traffic conditions.
In one embodiment, scheduling packets are exchanged among neighboring nodes of a computer network. These scheduling packets include descriptions of a transmitting node""s 2-hop neighborhood within the computer network, and nodes are able to determine transmission schedules from information received via said scheduling packets. Preferably, the computer network is a synchronized network in which time is divided into a number of frames, each of which are made up of a plurality of slots. In such cases, the exchange of scheduling packets should occur within a first number of the slots of each frame, preferably in a common communication channel. Transmission schedules may be determined, at least in part, because nodes advertise their availability using the scheduling packets.
The above-mentioned descriptions may include an identification of received communication times and/or channels, an identification of requested communication times and/or channels and an identification of available communication times and/or channels. The requested communication times and/or channels should correspond to available times and/or channels advertised by one or more nodes of the computer network. In this scheme, the identification of reserved communication times and/or channels should be made after eliminating any conflicting scheduled transmissions for those communication times and/or channels.
A further embodiment allow for scheduling transmission times and/or channels at a node of a computer network according to previously reserved and requested transmission schedules received in packets transmitted by neighboring nodes of the computer network. Such packets are transmitted at the beginning of each frame period within the computer network and transmission times and/or channels are scheduled for periods indicated as being available according to information included in the packets. In one implementation of this scheme, previously reserved transmission schedules have precedence over the requested transmission schedules and conflicts between requested transmission schedules are resolved according to a priority scheme.
Under the priority scheme, requested broadcast transmissions have precedence over requested multicast or unicast transmissions. In turn, requested multicast transmissions have precedence over requested unicast transmissions. Any conflicts between requested transmissions of equal precedence based on transmission type are resolved according to schedule priority tickets included in the packets and accommodating requested transmission schedules takes precedence over reserving listening time at the node.
Still another embodiment involves determining a transmit/receive schedule at a node of a computer network by first monitoring a common communication channel within the computer network to determine from information included within packets transmitted within the common communication channel previously scheduled transmission times and/or channels and advertised listening times of neighboring nodes in the computer network. The information included within the packets should include a list of the neighboring nodes"" scheduled outbound communications, a list of the neighboring nodes"" scheduled inbound communications and a list of the neighboring nodes"" idle communication periods. The list of the neighboring nodes"" outbound communications may specify, for each outbound communication, an indication of the node to which the communication pertains, time parameters for the communication, channel parameters for the communication and a priority indication for the communication. Such a list may also include, for each outbound communication, an indication of whether the scheduled outbound communication has been established or requested. Similarly, the list of the neighboring nodes"" inbound communications may specify, for each inbound communication, an indication of the node to which the communication pertains, time parameters for the communication, channel parameters for the communication, a priority indication for the communication and, optionally, an indication of whether the scheduled inbound communication has been established or requested.
Under this scheme then, the information included within packets transmitted within the common communication channel includes, for each packet transmitted by a node, a list of neighboring nodes of the node transmitting the subject packet. This list of neighboring nodes may specify MAC addresses of those neighboring nodes, local link identifiers assigned by the node transmitting the subject packet and/or one of its neighboring nodes.
In the present scheme, the transmit/receive schedule is determined using a working schedule made up of a set of valid transmission times and/or channels and a feasible schedule including a set of valid listening times and/or channels. The working and feasible schedules are updated upon receipt of each of the packets. In particular, the working schedule is updated according to a protocol in which established communication times and/or channels between nodes of the network take precedence over requested communication times and/or channels. Under this protocol communication schedules for broadcast transmissions take precedence over those for multicast transmissions which, in turn, take precedence over those for unicast transmissions. Moreover, nodes of the network may only schedule one communication session with other nodes of the network during a particular time/channel period. The feasible schedule is updated according to a protocol in which established and/or requested communication sessions between nodes of the network take precedence over listening times.
Any communication session between nodes of the network should occupy contiguous time periods over a designated channel. Requested communication sessions are added to the working schedule after verifying that the requested sessions can be accommodated using the feasible schedule.
In still another embodiment a computer network includes two or more nodes configured to schedule communication sessions amongst themselves according to information regarding other communication sessions within 2-hop neighborhoods of the nodes within the computer network received over a common communication channel within the computer network. The two or more nodes may be configured to schedule the communication sessions amongst themselves by choosing communication times and/or channels advertised as being available. Further, the nodes should be configured to maintain working schedules, which list valid transmission times and/or channels previously established or requested by nodes of the network, and feasible schedules, which list valid listening times and/or channels of nodes of the network. Thus, the two or more nodes may be configured to add their own requested communication sessions to their respective working schedules only after verifying availability of time/channel parameters of such requested communication sessions with information from their respective feasible schedules and to exchange working schedules as part of the informing transferred within the common communication channel.